/*

-- Привет --
Третий спринт - сплошная боль и перебор значений, чтобы наконец что-то получилось.
Даже под конец спринта и после финальных я все равно не смог "увидеть/представить"
рекурсию, чтобы ее нормально писать. Но пока что задания сделал и получил ОК

// Задача: A.Поиск в сломанном массиве
// Компилятор: (make) Node.js 18.16.0
// Вердикт: OK
// Статус: Полное решение
// https://contest.yandex.ru/contest/23815/run-report/109499164/


-- ПРИНЦИП РАБОТЫ --
В целом, буквально брал из теории решение и адаптировал, обрабатывая случаи крайние.
Создает указатели начала и конца, берем серединное значение, если это то, что нужно - возвращаем
если нет - проверяем левую часть, при этом проверяя начало и конец этой части, если что - сдвигает ее начало или конец
в другом случае делаем то же самое с правой частью.
Если не нашлось числ - возвращаем -1

-- ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ --
Сложность O(logn), поскольку мы каждый раз делим пополам и работаем отдельно с каждой
половиной, в последствии дробя дальше. 


-- ВРЕМЕННАЯ СЛОЖНОСТЬ --
Добавление и удаление в/из деки стоит O(1), поскольку каждый раз начало и конец смещается, что не побуждает "массив"
переставлять значения при его изменении

-- ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ --
В данном случае простраственная сложность равна O(n), поскольку мы работаем с массивом определенной длины

*/

function brokenSearch(arr, k) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === k) {
      return mid;
    }

    if (arr[start] <= arr[mid]) {
      if (k >= arr[start] && k < arr[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    } else {
      if (k > arr[mid] && k <= arr[end]) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
  }

  return -1;
}

function test() {
  const arr = [19, 21, 100, 101, 1, 4, 5, 7, 12];
  if (brokenSearch(arr, 5) !== 6) {
    console.error("WA");
  }
}
